package 力扣.动态规划;
//有一堆石头，每块石头的重量都是正整数。
//每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
//    如果 x == y，那么两块石头都会被完全粉碎；
//    如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
//最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。
public class 最后一块石头的重量 {
    public static void main(String[] args) {
         int[] stones={2,7,4,1,8,1};
        int i = lastStoneWeightII(stones);
        System.out.println(i);
    }
    public static int lastStoneWeightII(int[] stones) {
        int len=stones.length;
        int sum=0;
        for (int w: stones) {
           sum+=w;
        }
        int[] dp = new int[sum / 2 + 1];
        for (int i = 0; i < len; i++) {
            int stone=stones[i];
            for (int j=sum/2;j>=stone;j--)
                dp[j]=Math.max(dp[j],dp[j-stone]+stone);
        }
        return sum-dp[sum/2]*2;
    }
}
